The present invention relates to signal processing using time compressors, time inverters, convolvers, matched filters, correlators and multipliers and more particularly to digital signal processing in which the signals are represented by a series of coded digits, for example digits found at the output of an analog-to-digital converter.
Special purpose digital equipment often needs to perform the computations of convolution, matched filtering, cross-correlation and the discrete Fourier transform. These transforms present an excessive computational load for a general purpose computer and a heavy load even for a digital computer structured for signal processing. For example, a straightforward linear transformation in a computer that takes a sequence of N data points into a sequence of N transform points made be regarded as a multiplication by a vector N.sup.2 matrix. A direct implementation that uses a single multiplier requires N.sup.2 multiplication times and N.sup.2 words of storage. The Fast Fourier transform (FFT) offers some advantage in that it requires a number of multiplications proportional to N log.sub.2 N.
Signal processors are known in the art wherein convolutions, matched filtering, cross correlation and the discrete Fourier transform are computed in a general purpose computer or in a digital computer especially structured for signal processing. An example of a specially structured computer can be seen in U.S. Pat. No. 3,748,451. As noted previously however, such computations present excessive or heavy loads for such computers. As example, if the execution time of a digital computer which uses a software program is 10 microsecond/operation then the execution of a fast convolution in a serial processor is N/100 log.sub.2 N milliseconds and this time becomes quite large even for modest values of N. Cascading, paralleling and arraying computers to shorten the execution time quickly increases the cost. As a consequence, while the computer using software has the potential it falls short in many applications which require short execution times and in many applications therefore which require operation in real time. The present invention is directed to a signal processor which can be obtained as a hardwired filter, i.e., utilizing all hardware means as opposed to computers usng software means. As a consequence, the present invention offers execution times on the order of 0.01 microsecond/operation or less and clearly extends the art to applications which cannot be serviced by the slower prior art using digital computers. In what follows therefore the term "prior art" will refer to devices other than digital computers using software, i.e., will refer only to hardwired filters.
A number of transform implementations are known in the hardwired filter art that have a simple serial data flow and a computation time proportional to N. These include convolution and correlation transforms and these are implemented using transversal filters as discussed in the paper by H. J. Whitehouse et al "High Speed Serial Access Linear Transform Implementations" Naval Undersea Center, San Diego, California 92132, January, 1973. In general, apparatus in the prior art fall into two broad categories; those employing acoustic and those employing non-acoustic means. Included in the former category are sonic, magnetostrictive, acoustic surface wave, and optoacoustic filters, while the latter category comprises charge coupled devices (CCD) and binary shift registers (BSR). Acoustic filters have been described in the paper by W. D. Squire et al "Linear Signal Processing and Ultrasonic Transversal Filters" appearing in the November, 1969 issue of IEEE Transactions on Microwave Theory and Techniques, while non-acoustic filters have been described in the paper by G. W. Byram et al "Signal Processing Device Technology" appearing in the Proceedings of the NATO Advanced Study Institute on Signal Processing held at the University of Technology, Loughborough, U. K. on 21 Aug. through 1 Sept., 1972.
As a rule, if interruptions of the processing are infrequent, the acoustic filters are preferred since they offer large storage capacity, convenient tapping of delay lines, and low power dissipation. When short duration interruptions of the signal processing may occur, CCD with their controllable clock rates offer the advantages of small size, offset only by charge transfer inefficiency and temperature sensitivity. When frequent processing interrupts are required, digital implementations in the form of shift registers are indicated. The rapid development of solid state technology however favors digital and these now are available commercially.
Digital implementations in the prior art have been obtained to compute the convolution and correlation transforms but are confined to the use of shift registers playing the role of delay lines. These are described in the paper by H. J. Whitehouse and in the paper by J. J. Buie and D. R. Brewer "A Larger Scale Integrated Correlator" appearing in the October, 1972 issue of IEEE Journal of Solid State Circuits, SC-7. Digital correlation systems using shift registers are also shown in U.S. Pat. Nos. to C. Pryor 3,303,335, to G. Bush et al 3,351,943, to G. Lindsay et al 3,670,151, to J. Stitt 3,717,756, to A. Croissieur et al 3,777,130 and to J. Alsup et al 3,831,013. Digital implementations of multipliers are described in the foregoing references and in the two articles by G. Kostopoulos "Serial-Serial Multiplication" and "Serial-Parallel Multiplication" appearing in the April, 1973 issue of Digital Design. All such devices can be assembled from conventional medium scale logic (MSL) or can be designed in large scale integrated (LSI) form.
The digital implementation of convolvers, matched filters, correlators, and multipliers in the prior art requires the storage of data in shift registers providing at least 2N words of storage and having N multipliers for the computation of the desired transforms. Shift registers however are limited in size and speed and many similar devices are needed if much data must be stored. Metal oxide substrate (MOS) registers while providing high density require extra power supplies and are slow-speed when used as bipolar shift registers. Shift registers notoriously sacrifice delay taps to obtain long lengths of their registers and to mantain compactness. In all cases, the length of registers determines their capacity and speed.
In many signal processing applications, the signals must be compressed in time. This is accomplished in the prior art by storing signals in an acoustic delay line and then retrieving them at a rate which is greater than the rate of storage as explained in the article by W. D. Squire. Of particular usefulness is the delay line time compressor (DELTIC) circuit which recirculates signals is a number of recirculations. The recirculation requires less length of delay line and is therefore a more efficient system. My copending applications Ser. No. 435,681 filed Jan. 23, 1974 now abandoned and Ser. No. 479,872 filed June 17, 1974, the latter application being a continuation-in-part of the former, now U.S. Pat. No. 3,950,635, and Ser. No. 609,342 filed Sept. 2, 1975, this last application being a division of application Ser. No. 479,872, teach the time compression of signals in a digital (non-acoustic) DELTIC circuit with RAMs in the role of delay lines. The terms DELTIC BSR, DELTIC RAM, DELTIC ROM, DELTIC PROM will be utilized throughout the disclosure to indicate the use of binary shift registers (BSR), random access memories (RAM), read-only memories (ROM), programmable read-only memories (PROM) and so forth as the delay line elements in a digital DELTIC circuit.
In general, the prior digital art using shift registers utilize 2N words of storage and employ N multipliers for performing the convolution or correlation transforms of signals. The present invention using RAMs as delay line elements requires 2N and in some cases only N words of storage and only one multiplier and in this manner provides new and improved convolvers, matched filters and correlators while significantly decreasing the weight, size, power consumption and cost for such devices. Moreover, the use of a digital DELTIC circuit with RAMs further enhances the invention over the prior art. As will be presently seen, the outstanding difference between the system of the present invention and the prior art is its ability to time-invert signals and to provide twice the resolution otherwise available.
A common deficiency in the prior art is in providing a fixed coded reference. For example, in a correlator one provides a coded reference signal (a fixed or stationary reference signal) while in a matched filter one provides coded hardware (fixed hardware responding to the incoming signal). A way to circumvent this difficulty is now available using the fact that if two signals are propagated from opposite ends of a delay line a convolution of the two signals occurs, as explained in the paper by C. F. Quate and R. B. Thompson "Convolution and Correlation in Real Time with Non-Linear Acoustics" appearing in the June, 1970 issue of Applied Physics Letters and in U.S. Pat. to C. F. Quate No. 3,760,172 . A convolver provides a reference signal which itself moves or scans by the incoming signal and can be electronically varied to provide a large number of reference signals in a single device. Otherwise, a large number of different devices would be necessary to process a variety of incoming signals. The technique for obtaining convolution therefore is very useful because one device is capable of carying out a large number of sorting functions on a large number of incoming signals. For example, a coded reference signal can be used to detect a coded input signal and the reference signal can be electronically varied thus freeing the design from a large number of coded hardware implementations which is quite common in the prior art. The convolution technique is clearly an important new method for signal processing and has been demonstrated in the prior art using both acoustic and digital (shift register) means. It offers twice the resolution of previous techniques and as mentioned already it offers electronic variation of the coded reference signal. Significantly however, in passive receiver applications, it offers the remarkable feature that the signal itself may be used as its own reference, i.e., an incoming signal generates its own matched filter. This is by virtue of the fact that a convolution of a signal S(t) with its time-inversion S(-t) is a matched filtering, i.e., providing maximum output response with respect to thermal noise. The present invention extends the convolution technique beyond the prior art by using RAMs, DELTIC RAMs, ROMs, PROMs and BSRs as the delay line elements in digital convolvers and correlators.
In the prior art, implementation of the convolution transform have been obtained using the non-linear interaction between two acoustic waves propagating through an acoustic delay medium as explained in the article by G. Kino and H. Mathews "Signal Processing in Acoustic Surface Wave Devices" appearing in the August, 1971 issue of IEEE Spectrum and in the article by G. Kino and J. Shaw "Acoustic Surface Waves" appearing in the September, 1972 issue of Scientific American. Non-linear acoustic processing involves putting two signals into a surface or bulk acoustic type delay line from opposite ends of the line which then responds as the convolution of the two signals and thus making it unnecessary to design a fixed coded reference signal into the line. In this manner one can vary the scanning coded reference signal at will and thereby perform a wide range of signal processing operations. This then can be accomplished in the Quate-Thompson apparatus which is a single acoustic delay device. A dual tapped acoustic delay line having 2N words of storage and N multipliers has been suggested in the article by C. E. Cock "Preferred Mode for the Quate-Thompson Non-Linear Acoustic Correlator Device" appearing in the August, 1971 issue of the Proceedings IEEE (Lett). The paper by H. J. Whitehouse suggests a dual digital delay line using shift registers and having 2N words of storage and N multipliers. A convolution system using either acoustic or shift register digital delay lines is discussed in U.S. Pat. to C. Cook No. 3,774,019.
From the discussion above it is clear that in the past, the implementation of a convolver has been accomplished using acoustic means or using digital shift registers playing the role of delay lines and, for all practical purposes, has not been made commercially available being confined mostly to the laboratory. Furthermore, the prior art for the digital implementation of convolvers, matched filters and correlators falls short when the capacity, speed, cost and size of shift registers are considered in devices which require high data throughputs.
It is an object of the present invention to provide a digital convolver, matched filter, correlator and multiplier using RAMs or DELTIC RAMs and capable of exceeding the performance of prior art digital devices using BSRs, at reduced weight, size and cost.